package dp.一维数组;


import java.util.Arrays;

/**
 * https://leetcode.cn/problems/jump-game-ii/
 *
 * https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247485087&idx=1&sn=ddbed992e5ad8f1aa3b3d4afcb17889b&scene=21#wechat_redirect
 *
 * 题解：https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247493675&idx=1&sn=c3c1b01b40b64ad63d473666c263d280&chksm=9bd41623aca39f359a3a4b87139b539dc1c6157c1291300ec7756b1ff95f1edad27e6c12e557&scene=178&cur_album_id=2165170016067944448#rd
 */
public class _45_跳跃游戏II {

    public int jump(int[] nums) {
        meno = new int[nums.length - 1];
        Arrays.fill(meno, nums.length);
        return dp(nums, 0);
    }

    int[] meno;

    // 从索引p跳到最后一步，需要dp(nums,p)步
    private int dp(int[] nums, int p) {
        // 这边就是nums.length - 1步，因为刚开始的时候在0的位置，到最后nums.length就需要nums.length -1步
        if (p >= nums.length - 1) return 0;

        if (meno[p] != nums.length) return meno[p];

        int step = nums[p];

        for (int i = 1; i <= step; i++) {
            int subproblem = dp(nums, p + i);
            meno[p] = Math.min(subproblem + 1, meno[p]);
        }

        return meno[p];
    }
}
